package com.hdu.other.unionSet;

public class lc765 {
    class Solution {

        int[] father;
        int m;

        public int minSwapsCouples(int[] row) {
            int n = row.length;
            m = n / 2;
            this.father = new int[m];
            build();
            int seats = m;
            for (int i = 0; i < n; i += 2)
                union(row[i] / 2, row[i + 1] / 2);
            return seats - m;
        }

        void build() {
            for (int i = 0; i < m; i++)
                father[i] = i;
        }

        int find(int x) {
            if (x != father[x])
                father[x] = find(father[x]);
            return father[x];
        }

        void union(int x, int y) {
            if (find(x) != find(y)) {
                father[find(x)] = find(y);
                m--;
            }
        }

    }
}
